package com.easy.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName CombinationSum39
 * @Description 39. 组合总和
 * @Author zheng
 * @Date 2021/11/20 11:30
 * @Version 1.0
 **/
public class CombinationSum39 {
    /**
     * /存放路径
     **/
    List<Integer> path = new ArrayList<>();
    /**
     * /结果
     **/
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, target, 0, 0);
        return result;
    }

    /**
     * @return void
     * @Description
     * @Date 2021/11/20 16:30
     * @Param [candidates 数组, target 目标值, sum 当前和, startIndex 开始索引]
     **/
    public void helper(int[] candidates, int target, int sum, int startIndex) {
        //退出条件
        if (sum == target) {
            //记录当前值，注意：需要存放到新对象中
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历数组 ，
        // 剪枝 已排序数组， sum + candidates[i] <= target时，才继续，大于时后面的额数据都不可能满足条件
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            //记录和
            sum += candidates[i];
            //记录路径
            path.add(candidates[i]);
            //递归调用
            helper(candidates, target, sum, i);
            //从和里减去当前值，继续向下搜索
            sum -= candidates[i];
            //从搜索路径里删除当前值，继续向下搜索
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum39 combinationSum39 = new CombinationSum39();
        System.out.println(combinationSum39.combinationSum(new int[]{2,7,6,3,5,1}, 9).toString());
    }
}
